import java.util.*;

/**
 * @author LKQ
 * @date 2022/2/22 12:05
 * @description 优先队列，即小顶堆
 */
public class FormalSolution2 {
    public static void main(String[] args) {
        FormalSolution2 solution = new FormalSolution2();
        String[] words = {"i", "love", "leetcode", "i", "love", "coding"};
        solution.topKFrequent(words, 2);
    }
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> cnt = new HashMap<String, Integer>();
        for (String word : words) {
            cnt.put(word, cnt.getOrDefault(word, 0) + 1);
        }
        PriorityQueue<String> priorityQueue = new PriorityQueue<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (Objects.equals(cnt.get(o1), cnt.get(o2))) {
                    return o2.compareTo(o1);
                }else {
                    return cnt.get(o1) - cnt.get(o2);
                }
            }
        });
        for (Map.Entry<String, Integer> entry: cnt.entrySet()) {
            priorityQueue.offer(entry.getKey());
            if (priorityQueue.size() > k) {
                priorityQueue.poll();
            }
        }
        List<String> ret = new ArrayList<String>();
        while (k-- > 0) {
            ret.add(0, priorityQueue.poll());
        }
        return ret;
    }
}
